from typing import List

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        result = []
        used = [False] * len(nums)
        
        def backtrack(path: List[int]):
            # 当路径长度等于原数组长度时，说明找到了一个排列
            if len(path) == len(nums):
                result.append(path.copy())
                return
            
            # 遍历所有可能的选择
            for i in range(len(nums)):
                # 如果该元素已经在路径中，跳过
                if used[i]:
                    continue
                
                # 做选择
                used[i] = True
                path.append(nums[i])
                
                # 递归
                backtrack(path)
                
                # 撤销选择
                used[i] = False
                path.pop()
        
        backtrack([])
        return result    